SherbyNet - /page/wikibook/entry.mu

Micron Document

<!DOCTYPE html>

<title>Database transaction schedule</title>

</head>

<span id="openzim-page-title" class="mw-page-title-main"><span class="mw-page-title-main">Database transaction schedule</span></span>

</h1>

</header>

/* start https://en.wikipedia.org/ */

.mw-parser-output .hatnote{font-style:italic}.mw-parser-output div.hatnote{padding-left:1.6em;margin-bottom:0.5em}.mw-parser-output .hatnote i{font-style:normal}.mw-parser-output .hatnote+link+.hatnote{margin-top:-0.5em}@media print{body.ns-0 .mw-parser-output .hatnote{display:none!important}}

/* end https://en.wikipedia.org/ */

</style><div role="note" class="hatnote navigation-not-searchable">This article is about databases and transaction processing. For other uses, see <a href="Scheduling_(computing)" title="Scheduling (computing)">scheduling (computing)</a>.</div>

/* start https://en.wikipedia.org/ */

.mw-parser-output .ambox{border:1px solid #a2a9b1;border-left:10px solid #36c;background-color:#fbfbfb;box-sizing:border-box}.mw-parser-output .ambox+link+.ambox,.mw-parser-output .ambox+link+style+.ambox,.mw-parser-output .ambox+link+link+.ambox,.mw-parser-output .ambox+.mw-empty-elt+link+.ambox,.mw-parser-output .ambox+.mw-empty-elt+link+style+.ambox,.mw-parser-output .ambox+.mw-empty-elt+link+link+.ambox{margin-top:-1px}html body.mediawiki .mw-parser-output .ambox.mbox-small-left{margin:4px 1em 4px 0;overflow:hidden;width:238px;border-collapse:collapse;font-size:88%;line-height:1.25em}.mw-parser-output .ambox-speedy{border-left:10px solid #b32424;background-color:#fee7e6}.mw-parser-output .ambox-delete{border-left:10px solid #b32424}.mw-parser-output .ambox-content{border-left:10px solid #f28500}.mw-parser-output .ambox-style{border-left:10px solid #fc3}.mw-parser-output .ambox-move{border-left:10px solid #9932cc}.mw-parser-output .ambox-protection{border-left:10px solid #a2a9b1}.mw-parser-output .ambox .mbox-text{border:none;padding:0.25em 0.5em;width:100%}.mw-parser-output .ambox .mbox-image{border:none;padding:2px 0 2px 0.5em;text-align:center}.mw-parser-output .ambox .mbox-imageright{border:none;padding:2px 0.5em 2px 0;text-align:center}.mw-parser-output .ambox .mbox-empty-cell{border:none;padding:0;width:1px}.mw-parser-output .ambox .mbox-image-div{width:52px}@media(min-width:720px){.mw-parser-output .ambox{margin:0 10%}}@media print{body.ns-0 .mw-parser-output .ambox{display:none!important}}

/* end https://en.wikipedia.org/ */

</style>

<p>In the fields of <a href="Database" title="Database">databases</a> and <a href="Transaction_processing" title="Transaction processing">transaction processing</a> (transaction management), a <b>schedule</b> (or <b>history</b>) of a system is an abstract model to describe the order of <a href="Execution_(computing)" title="Execution (computing)">executions</a> in a set of transactions running in the system. Often it is a <i>list</i> of operations (actions) ordered by time, performed by a set of <a href="Database_transaction" title="Database transaction">transactions</a> that are executed together in the system. If the order in time between certain operations is not determined by the system, then a <i><a href="Partial_order" class="mw-redirect" title="Partial order">partial order</a></i> is used. Examples of such operations are requesting a read operation, reading, writing, aborting, <a href="Commit_(data_management)" title="Commit (data management)">committing</a>, requesting a <a href="Lock_(computer_science)" title="Lock (computer science)">lock</a>, locking, etc. Often, only a subset of the transaction operation types are included in a schedule.

</p><p>Schedules are fundamental concepts in database <a href="Concurrency_control" title="Concurrency control">concurrency control</a> theory. In practice, most general purpose database systems employ conflict-serializable and strict recoverable schedules.

</p>

<div class="mw-heading mw-heading2"><h2 id="Notation">Notation</h2></div>

<p>Grid notation:

</p>

<ul><li><b>Columns:</b> The different transactions in the schedule.</li>

<li><b>Rows:</b> The time order of operations (a.k.a., actions).</li></ul>

<p>Operations (a.k.a., actions):

</p>

<ul><li><b>R(X):</b> The corresponding transaction "reads" object X (i.e., it retrieves the data stored at X). This is done so that it can modify the data (e.g., X=X+4) during a "write" operation rather than merely overwrite it. When the schedule is represented as a list rather than a grid, the action is represented as <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle Ri(X)}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle Ri(X)}</annotation>

</semantics>

</math></span><img src="./e17d26b9c6746d7e84f2da1b0244f20cebb00033.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:6.356ex; height:2.843ex;" alt="{\displaystyle Ri(X)}" loading="lazy"></span> where <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle i}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle i}</annotation>

</semantics>

</math></span><img src="./add78d8608ad86e54951b8c8bd6c8d8416533d20.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:0.802ex; height:2.176ex;" alt="{\displaystyle i}" loading="lazy"></span> is a number corresponding to a specific transaction.</li>

<li><b>W(X):</b> The corresponding transaction "writes" to object X (i.e., it modifies the data stored at X). When the schedule is represented as a list rather than a grid, the action is represented as <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle Wi(X)}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle Wi(X)}</annotation>

</semantics>

</math></span><img src="./0f8ce0cfa1fd54127a0967af1b2bee035571aadf.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:7.027ex; height:2.843ex;" alt="{\displaystyle Wi(X)}" loading="lazy"></span> where <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle i}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle i}</annotation>

</semantics>

<li><b>Com.:</b> This represents a "commit" operation in which the corresponding transaction has successfully completed its preceding actions, and has made all its changes permanent in the database.</li></ul>

<p>Alternatively, a schedule can be represented with a <i><a href="Acyclic_directed_graph" class="mw-redirect" title="Acyclic directed graph">directed acyclic graph</a></i> (or DAG) in which there is an arc (i.e., <a href="Directed_edge" class="mw-redirect" title="Directed edge">directed edge</a>) between each <i><a href="Ordered_pair" title="Ordered pair">ordered pair</a></i> of operations.

</p>

<div class="mw-heading mw-heading3"><h3 id="Example">Example</h3></div>

<p>The following is an example of a schedule:

</p>

<caption>D

</caption>

<th>T1

</th>

<th>T2

</th>

<th>T3

</th></tr>

<tr>

<td>R(X)

</td>

<td>

</td>

<td>

</td></tr>

<tr>

<td>W(X)

</td>

<td>

</td>

<td>

</td></tr>

<tr>

<td>Com.

</td>

<td>

</td>

<td>

</td></tr>

<tr>

<td>

</td>

<td>R(Y)

</td>

<td>

</td></tr>

<tr>

<td>

</td>

<td>W(Y)

</td>

<td>

</td></tr>

<tr>

<td>

</td>

<td>Com.

</td>

<td>

</td></tr>

<tr>

<td>

</td>

<td>

</td>

<td>R(Z)

</td></tr>

<tr>

<td>

</td>

<td>

</td>

<td>W(Z)

</td></tr>

<tr>

<td>

</td>

<td>

</td>

<td>Com.

</td></tr></tbody></table>

<p>In this example, the columns represent the different transactions in the schedule D. Schedule D consists of three transactions T1, T2, T3. First T1 Reads and Writes to object X, and then Commits. Then T2 Reads and Writes to object Y and Commits, and finally, T3 Reads and Writes to object Z and Commits.

</p><p>The schedule D above can be represented as list in the following way:

</p><p>D = R1(X) W1(X) Com1 R2(Y) W2(Y) Com2 R3(Z) W3(Z) Com3

</p>

<div class="mw-heading mw-heading2"><h2 id="Duration_and_order_of_actions">Duration and order of actions</h2></div>

<p>Usually, for the purpose of reasoning about concurrency control in databases, an operation is modelled as <i><a href="Atomicity_(database_systems)" title="Atomicity (database systems)">atomic</a></i>, occurring at a point in time, without duration. Real executed operations always have some duration.

</p><p>Operations of transactions in a schedule can interleave (i.e., transactions can be executed <a href="Concurrency_(computer_science)" title="Concurrency (computer science)">concurrently</a>), but time orders between operations in each transaction must remain unchanged. The schedule is in <i><a href="Partial_order" class="mw-redirect" title="Partial order">partial order</a></i> when the operations of transactions in a schedule interleave (i.e., when the schedule is conflict-serializable but not serial). The schedule is in <i><a href="Partial_order" class="mw-redirect" title="Partial order">total order</a></i> when the operations of transactions in a schedule do not interleave (i.e., when the schedule is serial).

</p>

<div class="mw-heading mw-heading2"><h2 id="Types_of_schedule">Types of schedule</h2></div>

<p>A <b>complete schedule</b> is one that contains either an abort (a.k.a. <b><a href="Rollback_(data_management)" title="Rollback (data management)">rollback</a>)</b> or commit action for each of its transactions. A transaction's last action is either to commit or abort. To maintain <a href="Atomicity_(database_systems)" title="Atomicity (database systems)">atomicity</a>, a transaction must undo all its actions if it is aborted.

</p>

<div class="mw-heading mw-heading3"><h3 id="Serial">Serial</h3></div>

<p>A schedule is <b>serial</b> if the executed transactions are non-interleaved (i.e., a serial schedule is one in which no transaction starts until a running transaction has ended).

</p><p>Schedule D is an example of a serial schedule:

</p>

<caption>D

</caption>

<th>T1

</th>

<th>T2

</th>

<th>T3

</th></tr>

<tr>

<td>R(X)

</td>

<td>

</td>

<td>

</td></tr>

<tr>

<td>W(X)

</td>

<td>

</td>

<td>

</td></tr>

<tr>

<td>Com.

</td>

<td>

</td>

<td>

</td></tr>

<tr>

<td>

</td>

<td>R(Y)

</td>

<td>

</td></tr>

<tr>

<td>

</td>

<td>W(Y)

</td>

<td>

</td></tr>

<tr>

<td>

</td>

<td>Com.

</td>

<td>

</td></tr>

<tr>

<td>

</td>

<td>

</td>

<td>R(Z)

</td></tr>

<tr>

<td>

</td>

<td>

</td>

<td>W(Z)

</td></tr>

<tr>

<td>

</td>

<td>

</td>

<td>Com.

</td></tr></tbody></table>

<div class="mw-heading mw-heading3"><h3 id="Serializable">Serializable</h3></div>

<p>A schedule is <b>serializable</b> if it is equivalent (in its outcome) to a serial schedule.

</p><p>In schedule E, the order in which the actions of the transactions are executed is not the same as in D, but in the end, E gives the same result as D.

</p>

<caption>E

</caption>

<th>T1

</th>

<th>T2

</th>

<th>T3

</th></tr>

<tr>

<td>R(X)

</td>

<td>

</td>

<td>

</td></tr>

<tr>

<td>

</td>

<td>R(Y)

</td>

<td>

</td></tr>

<tr>

<td>

</td>

<td>

</td>

<td>R(Z)

</td></tr>

<tr>

<td>W(X)

</td>

<td>

</td>

<td>

</td></tr>

<tr>

<td>

</td>

<td>W(Y)

</td>

<td>

</td></tr>

<tr>

<td>

</td>

<td>

</td>

<td>W(Z)

</td></tr>

<tr>

<td>Com.

</td>

<td>Com.

</td>

<td>Com.

</td></tr></tbody></table>

<p>Serializability is used to keep the data in the data item in a consistent state. It is the major criterion for the correctness of concurrent transactions' schedule, and thus supported in all general purpose database systems. Schedules that are not serializable are likely to generate erroneous outcomes; which can be extremely harmful (e.g., when dealing with money within banks).<sup id="cite_ref-Bernstein872_1-0" class="reference"><a href="#cite_note-Bernstein872-1"><span class="cite-bracket">[</span>1<span class="cite-bracket">]</span></a></sup><sup id="cite_ref-Weikum012_2-0" class="reference"><a href="#cite_note-Weikum012-2"><span class="cite-bracket">[</span>2<span class="cite-bracket">]</span></a></sup><sup id="cite_ref-Herlihy1993_3-0" class="reference"><a href="#cite_note-Herlihy1993-3"><span class="cite-bracket">[</span>3<span class="cite-bracket">]</span></a></sup>

</p><p>If any specific order between some transactions is requested by an application, then it is enforced independently of the underlying serializability mechanisms. These mechanisms are typically indifferent to any specific order, and generate some unpredictable <a href="Partial_order" class="mw-redirect" title="Partial order">partial order</a> that is typically compatible with multiple serial orders of these transactions.

</p>

<div class="mw-heading mw-heading4"><h4 id="Conflicting_actions">Conflicting actions</h4></div>

<p>Two actions are said to be in conflict (conflicting pair) if and only if all of the 3 following conditions are satisfied:

</p>

<ol><li>The actions belong to different transactions.</li>

<li>At least one of the actions is a write operation.</li>

<li>The actions access the same object (read or write).<sup id="cite_ref-:0_4-0" class="reference"><a href="#cite_note-:0-4"><span class="cite-bracket">[</span>4<span class="cite-bracket">]</span></a></sup><sup id="cite_ref-5" class="reference"><a href="#cite_note-5"><span class="cite-bracket">[</span>5<span class="cite-bracket">]</span></a></sup></li></ol>

<p>Equivalently, two actions are considered conflicting if and only if they are <a href="Commutative_property" title="Commutative property">noncommutative</a>. Equivalently, two actions are considered conflicting if and only if they are a <a href="Read%E2%80%93write_conflict" title="Read–write conflict">read-write</a>, <a href="Write%E2%80%93read_conflict" title="Write–read conflict">write-read</a>, or <a href="Write%E2%80%93write_conflict" title="Write–write conflict">write-write</a> conflict.

</p><p>The following set of actions is conflicting:

</p>

<ul><li>R1(X), W2(X), W3(X) (3 conflicting pairs)</li></ul>

<p>While the following sets of actions are not conflicting:

</p>

<p>Reducing conflicts, such as through commutativity, enhances performance because conflicts are the fundamental cause of delays and aborts.

</p><p>The conflict is <b>materialized</b> if the requested conflicting operation is actually executed: in many cases a requested/issued conflicting operation by a transaction is delayed and even never executed, typically by a <a href="Lock_(computer_science)" title="Lock (computer science)">lock</a> on the operation's object, held by another transaction, or when writing to a transaction's temporary private workspace and materializing, copying to the database itself, upon commit; as long as a requested/issued conflicting operation is not executed upon the database itself, the conflict is <b>non-materialized</b>; non-materialized conflicts are not represented by an edge in the precedence graph.

</p>

<div class="mw-heading mw-heading4"><h4 id="Conflict_equivalence">Conflict equivalence</h4></div>

<p>The schedules S1 and S2 are said to be conflict-equivalent if and only if both of the following two conditions are satisfied:

</p>

<ol><li>Both schedules S1 and S2 involve the same set of transactions such that each transaction has the same actions in the same order.</li>

<li>Both schedules have the same set of conflicting pairs (such that the actions in each conflicting pair are in the same order).<sup id="cite_ref-6" class="reference"><a href="#cite_note-6"><span class="cite-bracket">[</span>6<span class="cite-bracket">]</span></a></sup> This is equivalent to requiring that all conflicting operations (i.e., operations in any conflicting pair) are in the same order in both schedules.</li></ol>

<p>Equivalently, two schedules are said to be conflict equivalent if and only if one can be transformed to another by swapping pairs of non-conflicting operations (whether adjacent or not) while maintaining the order of actions for each transaction.<sup id="cite_ref-:0_4-1" class="reference"><a href="#cite_note-:0-4"><span class="cite-bracket">[</span>4<span class="cite-bracket">]</span></a></sup>

</p><p>Equivalently, two schedules are said to be conflict equivalent if and only if one can be transformed to another by swapping pairs of non-conflicting adjacent operations with different transactions.<sup id="cite_ref-7" class="reference"><a href="#cite_note-7"><span class="cite-bracket">[</span>7<span class="cite-bracket">]</span></a></sup>

</p>

<div class="mw-heading mw-heading4"><h4 id="Conflict-serializable">Conflict-serializable</h4></div>

<p>A schedule is said to be <b>conflict-serializable</b> when the schedule is conflict-equivalent to one or more serial schedules.

</p><p>Equivalently, a schedule is conflict-serializable if and only if its <a href="Precedence_graph" title="Precedence graph">precedence graph</a> is acyclic when only committed transactions are considered. Note that if the graph is defined to also include uncommitted transactions, then cycles involving uncommitted transactions may occur without conflict serializability violation.

</p><p>The schedule K is conflict-equivalent to the serial schedule <T1,T2>, but not <T2,T1>.

</p>

<caption>K

</caption>

<th>T1

</th>

<th>T2

</th></tr>

<tr>

<td>R(A)

</td>

<td>

</td></tr>

<tr>

<td>

</td>

<td>R(A)

</td></tr>

<tr>

<td>W(B)

</td>

<td>

</td></tr>

<tr>

<td>Com.

</td>

<td>

</td></tr>

<tr>

<td>

</td>

<td>W(A)

</td></tr>

<tr>

<td>

</td>

<td>Com.

</td></tr></tbody></table>

<p>Conflict serializability can be enforced by restarting any transaction within the cycle in the precedence graph, or by implementing <a href="Two-phase_locking" title="Two-phase locking">two-phase locking</a>, <a href="Timestamp-based_concurrency_control" title="Timestamp-based concurrency control">timestamp ordering</a>, or <a href="Snapshot_isolation#Workarounds" title="Snapshot isolation">serializable snapshot isolation</a>.<sup id="cite_ref-Cahill082_8-0" class="reference"><a href="#cite_note-Cahill082-8"><span class="cite-bracket">[</span>8<span class="cite-bracket">]</span></a></sup>

</p>

<div class="mw-heading mw-heading4"><h4 id="View_equivalence">View equivalence</h4></div>

<p>Two schedules S1 and S2 are said to be view-equivalent when the following conditions are satisfied:

</p>

<ol><li>If the transaction <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle T_{i}}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle T_{i}}</annotation>

</semantics>

</math></span><img src="./a8dd1c50cb9436474f83624c3f679ccf3eebbfef.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:2.157ex; height:2.509ex;" alt="{\displaystyle T_{i}}" loading="lazy"></span> in S1 reads an initial value for object X, so does the same transaction <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle T_{i}}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle T_{i}}</annotation>

</semantics>

<li>If the transaction <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle T_{i}}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle T_{i}}</annotation>

</semantics>

</math></span><img src="./a8dd1c50cb9436474f83624c3f679ccf3eebbfef.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:2.157ex; height:2.509ex;" alt="{\displaystyle T_{i}}" loading="lazy"></span> reads a value (for an object X) written by the transaction <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle T_{j}}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle T_{j}}</annotation>

</semantics>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle T_{i}}</annotation>

</semantics>

</math></span><img src="./a8dd1c50cb9436474f83624c3f679ccf3eebbfef.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:2.157ex; height:2.509ex;" alt="{\displaystyle T_{i}}" loading="lazy"></span> in S1 does the final write for object X, so does the same transaction <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle T_{i}}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle T_{i}}</annotation>

</semantics>

<p>Additionally, two view-equivalent schedules must involve the same set of transactions such that each transaction has the same actions in the same order.

</p><p>In the example below, the schedules S1 and S2 are view-equivalent, but neither S1 nor S2 are view-equivalent to the schedule S3.

</p>

<th colspan="2">S1

</th>

<th colspan="2">S2

</th>

<th colspan="2">S3

</th></tr>

<tr>

<th>T1

</th>

<th>T2

</th>

<th>T1

</th>

<th>T2

</th>

<th>T1

</th>

<th>T2

</th></tr>

<tr>

<td>R(A)

</td>

<td>

</td>

<td>R(A)

</td>

<td>

</td>

<td>R(A)

</td>

<td>

</td></tr>

<tr>

<td>W(A)

</td>

<td>

</td>

<td>W(A)

</td>

<td>

</td>

<td>W(A)

</td>

<td>

</td></tr>

<tr>

</td>

<td>

</td>

<td>

</td>

<td>R(A)

</td>

<td>

</td>

<td>R(A)

</td></tr>

<tr>

<td>W(B)

</td>

<td>

</td>

<td>

</td>

<td>W(A)

</td>

<td>

</td>

<td>W(A)

</td></tr>

<tr>

<td>Com.

</td>

<td>

</td>

</td>

<td>

</td>

<td>

</td>

</td></tr>

<tr>

<td>

</td>

<td>R(A)

</td>

<td>W(B)

</td>

<td>

</td>

<td>

</td>

<td>W(B)

</td></tr>

<tr>

<td>

</td>

<td>W(A)

</td>

<td>Com.

</td>

<td>

</td>

</td>

<td>

</td></tr>

<tr>

<td>

</td>

</td>

<td>

</td>

</td>

</td>

<td>

</td></tr>

<tr>

<td>

</td>

</td>

<td>

</td>

</td>

<td>Com.

</td>

<td>

</td></tr>

<tr>

<td>

</td>

<td>Com.

</td>

<td>

</td>

<td>Com.

</td>

<td>

</td>

<td>Com.

</td></tr></tbody></table>

<p>The conditions for S3 to be view-equivalent to S1 and S2 were not satisfied at the corresponding superscripts for the following reasons:

</p>

<ol><li>Failed the first condition of view equivalence because T1 read the initial value for B in S1 and S2, but T2 read the initial value for B in S3.</li>

<li>Failed the second condition of view equivalence because T2 read the value written by T1 for B in S1 and S2, but T1 read the value written by T2 for B in S3.</li>

<li>Failed the third condition of view equivalence because T2 did the final write for B in S1 and S2, but T1 did the final write for B in S3.</li></ol>

<p>To quickly analyze whether two schedules are view-equivalent, write both schedules as a list with each action's subscript representing which view-equivalence condition they match. The schedules are view equivalent if and only if all the actions have the same subscript (or lack thereof) in both schedules:

</p>

<ul><li>S1: R1(A)<sub>initial read</sub>, W1(A), R1(B)<sub>initial read</sub>, W1(B), Com1, R2(A)<sub>written by T1</sub>, W2(A)<sub>final write</sub>, R2(B)<sub>written by T1</sub>, W2(B)<sub>final write</sub>, Com2</li>

<li>S2: R1(A)<sub>initial read</sub>, W1(A), R2(A)<sub>written by T1</sub>, W2(A)<sub>final write</sub>, R1(B)<sub>initial read</sub>, W1(B), Com1, R2(B)<sub>written by T1</sub>, W2(B)<sub>final write</sub>, Com2</li>

<li>S3: R1(A)<sub>initial read</sub>, W1(A), R2(A)<sub>written by T1</sub>, W2(A)<sub>final write</sub>, <b>R2(B)<sub>initial read</sub>, W2(B), R1(B)<sub>written by T2</sub>, W1(B)<sub>final write</sub>,</b> Com1, Com2</li></ul>

<div class="mw-heading mw-heading4"><h4 id="View-serializable">View-serializable</h4></div>

<p>A schedule is <b>view-serializable</b> if it is view-equivalent to some serial schedule. Note that by definition, all conflict-serializable schedules are view-serializable.

</p>

<caption>G

</caption>

<th>T1

</th>

<th>T2

</th></tr>

<tr>

<td>R(A)

</td>

<td>

</td></tr>

<tr>

<td>

</td>

<td>R(A)

</td></tr>

<tr>

<td>W(B)

</td>

<td>

</td></tr></tbody></table>

<p>Notice that the above example (which is the same as the example in the discussion of conflict-serializable) is both view-serializable and conflict-serializable at the same time. There are however view-serializable schedules that are not conflict-serializable: those schedules with a transaction performing a <a href="Blind_write" title="Blind write">blind write</a>:

</p>

<caption>H

</caption>

<th>T1

</th>

<th>T2

</th>

<th>T3

</th></tr>

<tr>

<td>R(A)

</td>

<td>

</td>

<td>

</td></tr>

<tr>

<td>

</td>

<td>W(A)

</td>

<td>

</td></tr>

<tr>

<td>

</td>

<td>Com.

</td>

<td>

</td></tr>

<tr>

<td>W(A)

</td>

<td>

</td>

<td>

</td></tr>

<tr>

<td>Com.

</td>

<td>

</td>

<td>

</td></tr>

<tr>

<td>

</td>

<td>

</td>

<td>W(A)

</td></tr>

<tr>

<td>

</td>

<td>

</td>

<td>Com.

</td></tr></tbody></table>

<p>The above example is not conflict-serializable, but it is view-serializable since it has a view-equivalent serial schedule <T1,| T2,| T3>.

</p><p>Since determining whether a schedule is view-serializable is <a href="NP-complete" class="mw-redirect" title="NP-complete">NP-complete</a>, view-serializability has little practical interest.

</p>

<div class="mw-heading mw-heading3"><h3 id="Recoverable">Recoverable</h3></div>

<p>In a <b>recoverable schedule</b>, transactions only commit after all transactions whose changes they read have committed. A schedule becomes <b>unrecoverable</b> if a transaction <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle T_{i}}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle T_{i}}</annotation>

</semantics>

</math></span><img src="./a8dd1c50cb9436474f83624c3f679ccf3eebbfef.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:2.157ex; height:2.509ex;" alt="{\displaystyle T_{i}}" loading="lazy"></span> reads and relies on changes from another transaction <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle T_{j}}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle T_{j}}</annotation>

</semantics>

</math></span><img src="./27cdb9041c8aa769beb9153a48f41002297faacc.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.005ex; width:2.267ex; height:2.843ex;" alt="{\displaystyle T_{j}}" loading="lazy"></span>, and then <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle T_{i}}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle T_{i}}</annotation>

</semantics>

</math></span><img src="./a8dd1c50cb9436474f83624c3f679ccf3eebbfef.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:2.157ex; height:2.509ex;" alt="{\displaystyle T_{i}}" loading="lazy"></span> commits and <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle T_{j}}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle T_{j}}</annotation>

</semantics>

</p>

<th colspan="2">F

</th>

<th colspan="2">F2

</th>

<th colspan="2">J

</th></tr>

<tr>

<th>T1

</th>

<th>T2

</th>

<th>T1

</th>

<th>T2

</th>

<th>T1

</th>

<th>T2

</th></tr>

<tr>

<td>R(A)

</td>

<td>

</td>

<td>R(A)

</td>

<td>

</td>

<td>R(A)

</td>

<td>

</td></tr>

<tr>

<td>W(A)

</td>

<td>

</td>

<td>W(A)

</td>

<td>

</td>

<td>W(A)

</td>

<td>

</td></tr>

<tr>

<td>

</td>

<td>R(A)

</td>

<td>

</td>

<td>R(A)

</td>

<td>

</td>

<td>R(A)

</td></tr>

<tr>

<td>

</td>

<td>W(A)

</td>

<td>

</td>

<td>W(A)

</td>

<td>

</td>

<td>W(A)

</td></tr>

<tr>

<td>Com.

</td>

<td>

</td>

<td>Abort

</td>

<td>

</td>

<td>

</td>

<td>Com.

</td></tr>

<tr>

<td>

</td>

<td>Com.

</td>

<td>

</td>

<td>Abort

</td>

<td>Abort

</td>

<td>

</td></tr></tbody></table>

<p>These schedules are recoverable. The schedule F is recoverable because T1 commits before T2, that makes the value read by T2 correct. Then T2 can commit itself. In the F2 schedule, if T1 aborted, T2 has to abort because the value of A it read is incorrect. In both cases, the database is left in a consistent state.

</p><p>Schedule J is unrecoverable because T2 committed before T1 despite previously reading the value written by T1. Because T1 aborted after T2 committed, the value read by T2 is wrong. Because a transaction cannot be rolled-back after it commits, the schedule is unrecoverable.

</p>

<div class="mw-heading mw-heading4"><h4 id="Cascadeless">Cascadeless</h4></div>

<p><b>Cascadeless schedules</b> (a.k.a. "Avoiding Cascading Aborts (ACA) schedules") are schedules which avoid cascading aborts by disallowing <a href="Write%E2%80%93read_conflict" title="Write–read conflict">dirty reads</a>. <b>Cascading aborts</b> occur when one transaction's abort causes another transaction to abort because it read and relied on the first transaction's changes to an object. A <b>dirty read</b> occurs when a transaction reads data from uncommitted write in another transaction.<sup id="cite_ref-9" class="reference"><a href="#cite_note-9"><span class="cite-bracket">[</span>9<span class="cite-bracket">]</span></a></sup>

</p><p>The following examples are the same as the ones in the discussion on recoverable:

</p>

<th colspan="2">F

</th>

<th colspan="2">F2

</th></tr>

<tr>

<th>T1

</th>

<th>T2

</th>

<th>T1

</th>

<th>T2

</th></tr>

<tr>

<td>R(A)

</td>

<td>

</td>

<td>R(A)

</td>

<td>

</td></tr>

<tr>

<td>W(A)

</td>

<td>

</td>

<td>W(A)

</td>

<td>

</td></tr>

<tr>

<td>

</td>

<td>R(A)

</td>

<td>

</td>

<td>R(A)

</td></tr>

<tr>

<td>

</td>

<td>W(A)

</td>

<td>

</td>

<td>W(A)

</td></tr>

<tr>

<td>Com.

</td>

<td>

</td>

<td>Abort

</td>

<td>

</td></tr>

<tr>

<td>

</td>

<td>Com.

</td>

<td>

</td>

<td>Abort

</td></tr></tbody></table>

<p>In this example, although F2 is recoverable, it does not avoid

cascading aborts. It can be seen that if T1 aborts, T2 will have to

be aborted too in order to maintain the correctness of the schedule

as T2 has already read the uncommitted value written by T1.

</p><p>The following is a recoverable schedule which avoids cascading abort. Note, however, that the update of A by T1 is always lost (since T1 is aborted).

</p>

<caption>F3

</caption>

<th>T1

</th>

<th>T2

</th></tr>

<tr>

<td>

</td>

<td>R(A)

</td></tr>

<tr>

<td>R(A)

</td>

<td>

</td></tr>

<tr>

<td>W(A)

</td>

<td>

</td></tr>

<tr>

<td>

</td>

<td>W(A)

</td></tr>

<tr>

<td>Abort

</td>

<td>

</td></tr>

<tr>

<td>

</td>

<td>Commit

</td></tr></tbody></table>

<p>Note that this Schedule would not be serializable if T1 would be committed.

Cascading aborts avoidance is sufficient but not necessary for a schedule to be recoverable.

</p>

<div class="mw-heading mw-heading4"><h4 id="Strict">Strict</h4></div>

<p>A schedule is <b>strict</b> if for any two transactions T1, T2, if a write operation of T1 precedes a <i>conflicting</i> operation of T2 (either read or write), then the commit or abort event of T1 also precedes that conflicting operation of T2. For example, the schedule F3 above is strict.

</p><p>Any strict schedule is cascade-less, but not the converse. Strictness allows efficient recovery of databases from failure.

</p>

<div class="mw-heading mw-heading2"><h2 id="Serializability_class_relationships">Serializability class relationships</h2></div>

<p>The following expressions illustrate the hierarchical (containment) relationships between <a href="Serializability" class="mw-redirect" title="Serializability">serializability</a> and <a href="Serializability" class="mw-redirect" title="Serializability">recoverability</a> classes:

</p>

<ul><li>Serial ⊂ conflict-serializable ⊂ view-serializable ⊂ all schedules</li>

<li>Serial ⊂ strict ⊂ cascadeless (ACA) ⊂ recoverable ⊂ all schedules</li></ul>

<p>The <a href="Venn_diagram" title="Venn diagram">Venn diagram</a> (below) illustrates the above clauses graphically.

</p>

<ul><li><a href="Schedule_(project_management)" title="Schedule (project management)">Schedule (project management)</a></li>

<li><a href="Two-phase_locking" title="Two-phase locking">Strong strict two-phase locking</a> (SS2PL or Rigorousness).</li>

<li><a href="Snapshot_isolation#Making_Snapshot_Isolation_Serializable" title="Snapshot isolation">Making snapshot isolation serializable</a><sup id="cite_ref-Cahill082_8-1" class="reference"><a href="#cite_note-Cahill082-8"><span class="cite-bracket">[</span>8<span class="cite-bracket">]</span></a></sup> in <a href="Snapshot_isolation" title="Snapshot isolation">Snapshot isolation</a>.</li>

<li><a href="Global_serializability" title="Global serializability">Global serializability</a>, where the <i>Global serializability problem</i> and its proposed solutions are described.</li>

<li><a href="Linearizability" title="Linearizability">Linearizability</a>, a more general concept in <a href="Concurrent_computing" title="Concurrent computing">concurrent computing</a>.</li></ul>

<div class="mw-heading mw-heading2"><h2 id="References">References</h2></div>

/* start https://en.wikipedia.org/ */

.mw-parser-output .reflist{margin-bottom:0.5em;list-style-type:decimal}@media screen{.mw-parser-output .reflist{font-size:90%}}.mw-parser-output .reflist .references{font-size:100%;margin-bottom:0;list-style-type:inherit}.mw-parser-output .reflist-columns-2{column-width:30em}.mw-parser-output .reflist-columns-3{column-width:25em}.mw-parser-output .reflist-columns{margin-top:0.3em}.mw-parser-output .reflist-columns ol{margin-top:0}.mw-parser-output .reflist-columns li{page-break-inside:avoid;break-inside:avoid-column}.mw-parser-output .reflist-upper-alpha{list-style-type:upper-alpha}.mw-parser-output .reflist-upper-roman{list-style-type:upper-roman}.mw-parser-output .reflist-lower-alpha{list-style-type:lower-alpha}.mw-parser-output .reflist-lower-greek{list-style-type:lower-greek}.mw-parser-output .reflist-lower-roman{list-style-type:lower-roman}

/* end https://en.wikipedia.org/ */

</style><div class="reflist">

<li id="cite_note-Bernstein872-1"><span class="mw-cite-backlink"><b><a href="#cite_ref-Bernstein872_1-0">^</a></b></span> <span class="reference-text"><a href="Phil_Bernstein" title="Phil Bernstein">Philip A. Bernstein</a>, Vassos Hadzilacos, Nathan Goodman (1987): <a rel="nofollow" class="external text" href="http://research.microsoft.com/en-us/people/philbe/ccontrol.aspx"><i>Concurrency Control and Recovery in Database Systems</i></a> (free PDF download), Addison Wesley Publishing Company, <style data-mw-deduplicate="TemplateStyles:r1238218222">

/* start https://en.wikipedia.org/ */

.mw-parser-output cite.citation{font-style:inherit;word-wrap:break-word}.mw-parser-output .citation q{quotes:"\"""\"""'""'"}.mw-parser-output .citation:target{background-color:rgba(0,127,255,0.133)}.mw-parser-output .id-lock-free.id-lock-free a{background:url("./mw/Lock-green.svg")right 0.1em center/9px no-repeat}.mw-parser-output .id-lock-limited.id-lock-limited a,.mw-parser-output .id-lock-registration.id-lock-registration a{background:url("./mw/Lock-gray-alt-2.svg")right 0.1em center/9px no-repeat}.mw-parser-output .id-lock-subscription.id-lock-subscription a{background:url("./mw/Lock-red-alt-2.svg")right 0.1em center/9px no-repeat}.mw-parser-output .cs1-ws-icon a{background:url("./mw/Wikisource-logo.svg")right 0.1em center/12px no-repeat}body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-free a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-limited a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-registration a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-subscription a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .cs1-ws-icon a{background-size:contain;padding:0 1em 0 0}.mw-parser-output .cs1-code{color:inherit;background:inherit;border:none;padding:inherit}.mw-parser-output .cs1-hidden-error{display:none;color:var(--color-error,#d33)}.mw-parser-output .cs1-visible-error{color:var(--color-error,#d33)}.mw-parser-output .cs1-maint{display:none;color:#085;margin-left:0.3em}.mw-parser-output .cs1-kern-left{padding-left:0.2em}.mw-parser-output .cs1-kern-right{padding-right:0.2em}.mw-parser-output .citation .mw-selflink{font-weight:inherit}@media screen{.mw-parser-output .cs1-format{font-size:95%}html.skin-theme-clientpref-night .mw-parser-output .cs1-maint{color:#18911f}}@media screen and (prefers-color-scheme:dark){html.skin-theme-clientpref-os .mw-parser-output .cs1-maint{color:#18911f}}

/* end https://en.wikipedia.org/ */

</style><a href="ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <bdi>0-201-10715-5</bdi></span>

</li>

<li id="cite_note-Weikum012-2"><span class="mw-cite-backlink"><b><a href="#cite_ref-Weikum012_2-0">^</a></b></span> <span class="reference-text"><a href="Gerhard_Weikum" title="Gerhard Weikum">Gerhard Weikum</a>, Gottfried Vossen (2001): <a rel="nofollow" class="external text" href="http://www.elsevier.com/wps/find/bookdescription.cws_home/677937/description#description"><i>Transactional Information Systems</i></a>, Elsevier, <a href="ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <bdi>1-55860-508-8</bdi></span>

</li>

<li id="cite_note-Herlihy1993-3"><span class="mw-cite-backlink"><b><a href="#cite_ref-Herlihy1993_3-0">^</a></b></span> <span class="reference-text"><a href="Maurice_Herlihy" title="Maurice Herlihy">Maurice Herlihy</a> and J. Eliot B. Moss. <i>Transactional memory: architectural support for lock-free data structures.</i> Proceedings of the 20th annual international symposium on Computer architecture (ISCA '93). Volume 21, Issue 2, May 1993.</span>

</li>

<li id="cite_note-:0-4"><span class="mw-cite-backlink">^ <a href="#cite_ref-:0_4-0"><sup><i><b>a</b></i></sup></a> <a href="#cite_ref-:0_4-1"><sup><i><b>b</b></i></sup></a></span> <span class="reference-text"><cite class="citation web cs1"><a rel="nofollow" class="external text" href="https://www.geeksforgeeks.org/conflict-serializability-in-dbms/">"Conflict Serializability in DBMS"</a>. <i>GeeksforGeeks</i>. 2015-12-29<span class="reference-accessdate">. Retrieved <span class="nowrap">2023-11-27</span></span>.</cite></span>

</li>

<li id="cite_note-5"><span class="mw-cite-backlink"><b><a href="#cite_ref-5">^</a></b></span> <span class="reference-text"><cite id="CITEREFSilberschatzKorthSudarshan2020" class="citation book cs1">Silberschatz, Abraham; Korth, Henry F.; Sudarshan, S. (2020). <i>Database system concepts</i> (Seventh ed.). New York, NY: McGraw-Hill Education. p. 814. <a href="ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <bdi>978-1-260-08450-4</bdi>.</cite></span>

</li>

<li id="cite_note-6"><span class="mw-cite-backlink"><b><a href="#cite_ref-6">^</a></b></span> <span class="reference-text"><cite id="CITEREFRamakrishnanGehrke2000" class="citation book cs1">Ramakrishnan, Raghu; Gehrke, Johannes (2000). <i>Database management systems</i>. Computer science series (2nd ed.). Boston: McGraw-Hill. p. 540. <a href="ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <bdi>978-0-07-232206-4</bdi>.</cite></span>

</li>

<li id="cite_note-7"><span class="mw-cite-backlink"><b><a href="#cite_ref-7">^</a></b></span> <span class="reference-text"><cite id="CITEREFGarcia-MolinaUllmanWidom2009" class="citation book cs1">Garcia-Molina, Hector; Ullman, Jeffrey D.; Widom, Jennifer (2009). <i>Database systems: the complete book</i>. Pearson international edition (2nd ed.). Upper Saddle River, NJ: Pearson/Prentice Hall. pp. <span class="nowrap">891–</span>892. <a href="ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <bdi>978-0-13-187325-4</bdi>.</cite></span>

</li>

<li id="cite_note-Cahill082-8"><span class="mw-cite-backlink">^ <a href="#cite_ref-Cahill082_8-0"><sup><i><b>a</b></i></sup></a> <a href="#cite_ref-Cahill082_8-1"><sup><i><b>b</b></i></sup></a></span> <span class="reference-text">Michael J. Cahill, Uwe Röhm, Alan D. Fekete (2008): <a rel="nofollow" class="external text" href="http://portal.acm.org/citation.cfm?id=1376690">"Serializable isolation for snapshot databases"</a>, <i>Proceedings of the 2008 ACM SIGMOD international conference on Management of data</i>, pp. 729-738, Vancouver, Canada, June 2008, <a href="ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <bdi>978-1-60558-102-6</bdi> (SIGMOD 2008 best paper award)</span>

</li>

<li id="cite_note-9"><span class="mw-cite-backlink"><b><a href="#cite_ref-9">^</a></b></span> <span class="reference-text"><cite class="citation web cs1"><a rel="nofollow" class="external text" href="https://www.geeksforgeeks.org/cascadeless-in-dbms/">"Cascadeless in DBMS"</a>. <i>GeeksforGeeks</i>. 2019-08-06<span class="reference-accessdate">. Retrieved <span class="nowrap">2023-11-29</span></span>.</cite></span>

</li>

</ol></div></div></div><div><div class="zim-footer">

This article is issued from <a class="external text" title="Last edited on 2025-05-28" href="https://en.wikipedia.org/wiki/?title=Database_transaction_schedule&oldid=1292717811">Wikipedia</a>. The text is available under <a class="external text" href="https://creativecommons.org/licenses/by-sa/4.0/deed.en">Creative Commons Attribution-Share Alike 4.0</a> unless otherwise noted. Additional terms may apply for the media files.

</div>

</div></div>

</div>

</main>

</div>

</body></html>